class Solution(object):
    def expand(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        n = len(s)

        def search(i):
            if i == n:
                return ['']
            out = []
            if s[i] != '{':
                j = i
                while j < n:
                    if s[j] != '{':
                        j += 1
                    else:
                        break
                now_t = s[i: j]
                next_t = search(j)
                for item in next_t:
                    out.append(now_t + item)
            else:
                j = i
                while s[j] != '}':
                    j += 1
                t = s[i + 1: j].split(',')
                t.sort()
                next_t = search(j + 1)
                for t1 in t:
                    for t2 in next_t:
                        out.append(t1 + t2)
            return out

        out = search(0)
        return out


data = Solution()
s = "{a,b}c{d,e}f"
print(data.expand(s))
s = "abcd"
print(data.expand(s))
s = "{a,b,c}"
print(data.expand(s))